package sort;

public class QuickSort {
    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        int[] arr = new int[800000];
        initArr(arr);
        quickSort(arr, 0, arr.length - 1);
        //System.out.print(Arrays.toString(arr));
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间：" + (endTime - startTime) + "ms");

    }

    static void initArr(int[] arr) {

        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 8000000);
        }
    }
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotloc = Partition(arr, low, high);
            quickSort(arr, low, pivotloc - 1);
            quickSort(arr, pivotloc + 1, high);

        }
    }

    public static int Partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= pivot)
                --high;
            arr[low] = arr[high];
            while (low < high && arr[low] <= pivot)
                ++low;
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        return low;
    }
}
